/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._453;

import java.util.Arrays;

/**
 * 给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动可以使 n - 1 个元素增加 1。
 * <p>
 * 示例:
 * <p>
 * 输入:
 * [1,2,3]
 * <p>
 * 输出:
 * 3
 * <p>
 * 解释:
 * 只需要3次移动（注意每次移动会增加两个元素的值）：
 * <p>
 * [1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._453
 * @ClassName: MinimumMoves
 * @Author: linyaonan
 * @Date: 2019/12/30 15:55
 */
public class MinimumMoves {

    public int minMoves(int[] nums) {
        Arrays.sort(nums);
        int c = 0;
        int start = nums[0];
        int[] dp = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = dp[i - 1] + (nums[i] - start);
            start = nums[i];
        }
        for (int i : dp) {
            c += i;
        }
        return c;
    }

    public int minMoves2(int[] nums) {
        int min = nums[0];
        for (int num : nums) {
            if (num < min) {
                min = num;
            }
        }
        int c = 0;
        for (int num : nums) {
            c += (num - min);
        }
        return c;
    }
}
